#include <iostream>
#include <array>

using std::cout;
using std::endl;
using std::array;

// 使用暴力算法，求出最大子段和
template<size_t N>
void bf(const array<int, N> &arr)
{
    int max = arr[0];
    for(int i{}; i < arr.size(); i++){
        int tmp = 0;
        for(int j{i}; j < arr.size(); j++){
            tmp += arr[j];
            if(tmp > max){
                max = tmp;
            }
        }
        tmp = 0;
    }

    cout << "bf: " << max << endl;
}

/*
状态推导公式：
    1, -1, 1, 1, -4, 3, -5
    dp[0] = arr[0] = 1
    dp[1] = max(dp[0] + arr[1], arr[1]) = 0
    dp[2] = max(dp[1] + arr[2], arr[2]) = 1
    dp[3] = max(dp[2] + arr[3], arr[3]) = 2
    
    dp[i] = max(dp[i - 1] + arr[i], arr[i])
*/
template<size_t N>
void dynamic(const array<int, N> &arr)
{
    array<int, N> dp;
    dp[0] = arr[0];
    int max = dp[0];
    for(int i{1}; i < arr.size(); i++){
        dp[i] = std::max(dp[i - 1] + arr[i], arr[i]);
        if(dp[i] > max) max = dp[i];
    }

    cout << "dynamic: " << max << endl;
}

int main(int args, char *argv[])
{
    // array<int, 10> arr = {-1,  4,  7,  1,  8,  -3,  8,  0,  2,  6};
    // array<int, 7> arr = {1, -1, 1, 1, -4, 3, -5};
    array<int, 10> arr = {1, -1, 1, 1, -4, 3, -5, 10, -5, 20};
    bf(arr);
    dynamic(arr);
    return 0;
}